#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 300. 最长递增子序列.py
@time: 2022/1/11 21:08
@desc: https://leetcode-cn.com/problems/longest-increasing-subsequence/
> 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

@解题思路：
    1. dp，Ot(n2), Os(n)
    2. 二分， Ot(nlogn), Os(n)
'''


class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        n = len(nums)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

class Solution02:
    def lengthOfLIS(self, nums:list) -> int:
        # 1. 维护一个tail数组，这个数组是递增的
        n = len(nums)
        # 2. tail数组如何产生？
        #   a. 将数组第一个数放入tail
        #   b. 遍历数组，将大于tail[-1]的数直接插入
        #   c. 若当前数组比tail[-1]的数就在tail中找到合适的位置替换，使得tail数组里的数字尽可能小

        # a. 将数组第一个数放入tail
        tail = [nums[0]]
        for i in range(1, n):
            # b. 遍历数组，将大于tail[-1]的数直接插入
            if nums[i]>tail[-1]:
                tail.append(nums[i])
                continue
            # c. 若当前数组比tail[-1]的数就在tail中找到合适的位置替换，使得tail数组里的数字尽可能小
            # 用二分进行查找
            left, right = 0, len(tail)-1
            while left<right:
                mid = (left+right)//2
                # 此处写成if nums[i]<tail[mid]: right = mid else: left = mid + 1时，若nums[i]==tail[mid]，会得到错误答案，或许是因为把nums[i]插入到mid+1了，但实际上应当替换mid
                if tail[mid]<nums[i]:
                    left = mid+1
                else:
                    right = mid
            # 找到替换位置
            tail[left] = nums[i]
        # 3. 答案就是tail的长度
        return len(tail)

if __name__ == '__main__':
    nums = [4, 10, 4, 3, 8, 9]
    res = Solution().lengthOfLIS(nums)
    print(res)